#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <ctime>

using namespace std;

//programming part 1=======================================================================

class trainStopData{
	string stop_id, stop_name;
	double stop_lat, stop_lon;
	public:
	trainStopData(const string& rawData){
		istringstream input(rawData);
		string token;
		getline(input,token,',');
		stop_id = token;
		getline(input,token,',');//junk i dont need
		getline(input,token,',');
		stop_name = token;
		getline(input,token,',');//junk i don't need
		getline(input,token,',');
		stop_lat = atof(token.c_str());
		getline(input,token,',');
		stop_lon = atof(token.c_str());
	}
	friend ostream& operator<<(ostream& os, const trainStopData& tsd);

	string get_id(){
		return stop_id;
	}
	string get_stop_name(){
		return stop_name;
	}
	double get_latitude(){
		return stop_lat;
	}
	double get_longitude(){
		return stop_lon;
	}
};

ostream& operator<<(ostream& os, const trainStopData& tsd){
	os << tsd.stop_id << " " << tsd.stop_name << " " << tsd.stop_lat << " " << tsd.stop_lon;
	return os;
}

//programming part 2=======================================================================

// timer class
class timer {
	public:
		timer() : start(clock()) {}
		double elapsed() { return ( clock() - start ) / CLOCKS_PER_SEC; }
		void reset() { start = clock(); }
	private:
		double start;
};


// Linear maximum contiguous subsequence sum algorithm.
// Comparable: must have constructor from int, must have
//     += and > defined, must have copy constructor
//     and operator=, and must have all properties
//     needed for vector.
// seqStart and seqEnd represent the actual best sequence.
	template <class Comparable>
Comparable maxSubsequenceSum4( const vector<Comparable> & a, int & seqStart, int & seqEnd )
{
	int n = a.size( );
	Comparable thisSum = 0;
	Comparable maxSum = 0;

	for( int i = 0, j = 0; j < n; j++ )
	{
		thisSum += a[ j ];

		if( thisSum > maxSum )
		{
			maxSum = thisSum;
			seqStart = i;
			seqEnd = j;
		}
		else if( thisSum < 0 )
		{
			i = j + 1;
			thisSum = 0;
		}
	}
	return maxSum;
}



// Quadratic maximum contiguous subsequence sum algorithm.
// Comparable: must have constructor from int, must have
//     += and > defined, must have copy constructor
//     and operator=, and must have all properties
//     needed for vector.
// seqStart and seqEnd represent the actual best sequence.
	template <class Comparable>
Comparable maxSubsequenceSum2( const vector<Comparable> & a,int & seqStart, int & seqEnd )
{
	int n = a.size( );
	Comparable maxSum = 0;

	for( int i = 0; i < n; i++ )
	{
		Comparable thisSum = 0;
		for( int j = i; j < n; j++ )
		{
			thisSum += a[ j ];

			if( thisSum > maxSum )
			{
				maxSum = thisSum;
				seqStart = i;
				seqEnd = j;
			}
		}
	}

	return maxSum;
}



// Cubic maximum contiguous subsequence sum algorithm.
// Comparable: must have constructor from int, must have
//     += and > defined, must have copy constructor
//     and operator=, and must have all properties
//     needed for vector.
// seqStart and seqEnd represent the actual best sequence.
	template <class Comparable>
Comparable maxSubsequenceSum1( const vector<Comparable> & a, int & seqStart, int & seqEnd )
{
	int n = a.size( );
	Comparable maxSum = 0;

	for( int i = 0; i < n; i++ )
		for( int j = i; j < n; j++ )
		{
			Comparable thisSum = 0;
			for( int k = i; k <= j; k++ )
				thisSum += a[ k ];

			if( thisSum > maxSum )
			{
				maxSum = thisSum;
				seqStart = i;
				seqEnd = j;
			}
		}

	return maxSum;
}

vector<int> generateRandomVector(int n){
	vector<int> retVec;
	for(int i = 0; i <= n; ++i){
		retVec.push_back((rand() %  2001) - 1000);
	}
	return retVec;
}

int main(){
	//Problem 1
	ifstream ifs("MTA_train_stop_data.txt");
	if(!ifs){
		cerr << "No file :(" << endl;
		return -1;
	}

	vector<trainStopData> stops;

	string currentData;
	while(getline(ifs, currentData)){
		stops.push_back(trainStopData(currentData));
	}

	//problem 2
	//cout.precision(numeric_limits<double>::digits10+1);
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(12);
	cout << CLOCKS_PER_SEC << endl;
	for(int n = 128; n <= 4096; n*=2){ 
		cout << "For n = " << n << " -----------------------------" << endl;	
		vector<int> randVec = generateRandomVector(n);
		int ss, se;
		timer t;
		
		/*
		int max = maxSubsequenceSum1(randVec, ss, se);
		double time = t.elapsed();
		cout << "#1:\t" << ss << " to " << se << " = " << max << " in\t" << time << endl;
		*/
		
		double time = 0;
		int runs = 100;
		for(int i = 0; i < runs; ++i){
			t.reset();
			maxSubsequenceSum2(randVec, ss, se);
			time += t.elapsed();
		}
		cout << "Avg. time for O(n^2):\t \t" << (time/runs) <<endl;
		
		time = 0;
		runs = 1;
		for(int i = 0; i < runs; ++i){
			t.reset();
			maxSubsequenceSum4(randVec, ss, se);
			time += t.elapsed();
		}
		cout << "Avg. time for O(n):\t \t" << (time/runs) <<endl;
	}
}
